package com.zephyr.wing.huawei.od.alg;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    /**
     * [
     *  .Q..,
     *  ...Q,
     *  ..Q.,
     *  Q...]
     * @param args
     */
    public static void main(String[] args) {
        List<List<String>> res = solveNQueens(4);
        System.out.println(res);
    }

    public static List<List<String>> solveNQueens(int n) {
        char[][] arr = new char[n][n];
        for (int i = 0; i < arr.length; i++) {
            Arrays.fill(arr[i], '.');
        }

        List<List<String>> res = new ArrayList<>();
        backtrack(n, arr, res, 0);

        return res;
    }

    public static void backtrack(int n, char[][] arr, List<List<String>> res, int row) {

        if (n < 0) {
            return;
        }

        if (row == arr.length && n == 0) {
            List<String> list = new ArrayList<>();
            for (int q1 = 0; q1 < arr.length; q1++) {
                list.add(new String(arr[q1]));
            }
            res.add(list);
        }

        for (int i = row; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {

                if (validCanAdd(arr, i, j)) {
                    // 放
                    arr[i][j] = 'Q';
                    backtrack(n - 1, arr, res, i + 1);
                    // 回溯
                    arr[i][j] = '.';
                }

                // 不放
                backtrack(n, arr, res, i + 1);
            }
        }

    }

    public static boolean validCanAdd(char[][] arr, int i, int j) {

        int n = arr.length;
        for (int k = 0; k < n; k++) {

            if (arr[k][j] == 'Q' || arr[i][k] == 'Q') {
                return false;
            }
        }

        int k1 = i;
        int k2 = j;

        while (i > 0 && j > 0) {
            if (arr[--i][--j] == 'Q') {
                return false;
            }
        }

        i = k1;
        j = k2;

        while (i < arr.length - 1 && j < arr.length - 1) {
            if (arr[++i][++j] == 'Q') {
                return false;
            }
        }

        i = k1;
        j = k2;

        while (i > 0 && j < arr.length - 1) {
            if (arr[--i][++j] == 'Q') {
                return false;
            }
        }

        i = k1;
        j = k2;

        while (i < arr.length - 1 && j > 0 ) {
            if (arr[++i][--j] == 'Q') {
                return false;
            }
        }

        return true;
    }
}
